

	ORDONAREA UNEI SECVENTE TRIVALENTE
       ------------------------------------

	Ideea care sta la baza solutiei este urmatoarea:
	Calculam intai nr. de aparitii Nr_ap[x] pt. elementele x=1,2,3 din secventa de intrare. In
secventa ordonata a numerelor date vom avea Nr_ap[1] elemente egale cu 1, urmate de Nr_ap[2] ele-
mente egale cu 2 si Nr_ap[3] elemente egale cu 3.
	Spunem ca un element x este in locul unui element y daca pozitiacurenta a lui x este egala
cu pozitia unui element y in secventa ordonata. In cele ce urmeaza vom folosi notatia x:y cu sem-
nificatia "elementul x este in locul elementului y". Apoi vom calcula Nr_per[x,y], numarul de ele-
mente x in locul elementelor lui y pt. toate elementele x si y in aceasta situatie. Sa consideram
urmatorul algoritm:

Nr_sch:=0;
while S nu este sortat do 
begin

If exista x si y unul in locul celuilalt Then			{1}
Begin
Inc(Nr-sch);
Interschimba x cu y (x:y)'
Actualizeaza Nr_per [x,y] si Nr_per[y,x]
End
Else Begin
   If (Nr_per[1,2]>0) si (Nr_per[3,1]>0) Then			{2}
   Begin
   Interschimba o pereche de elemente 3:1 si 1:2
   Actualizeaza Nr_per[3,1] si Nr_per[1,2]
   Inc(Nr_sch,2);
   End;

   If (nr_per[2,1]>0) si (Nr_per[1,3]>0) Then			{3}
   Begin
   Interschimba o pereche de elemente 2:1 si 1:3;
   Actualizeaza Nr_per[2,1] si Nr_per [1,3]
   Inc(Nr_sch,2);
   End;
     End;
end;

unde situatiile {1},{2},{3} corespund in ordine la:
.....x...y.....      ....3...1...2       .....2....3....1   <- vector curent
.....y...x.....      ....1...2...3       .....1....2....3   <- vector final (ordonat)

	Observam ca in situatia {1} 2 elemente care nu se afla "la locul lor" vor fi aduse pe
pozitiile lor finale, iar in situatiile {2} si {3} vor fi luate in calcul doar daca nu suntem
in situatia {1}, doar un element (a carui valoare este 1) este adus pe pozitia sa finala. De
aceea putem considera ca algoritmul de mai sus se incadreaza in metoda Greedy, deoarece se alege
mereu o interschimbare care aduce un numar maxim (2 sau 1) de elemente pe pozitiile lor finale.

	Incepem prin a arata ca nr. de operatii de interschimbare efectuat de algoritm este dat
de expresia:
Nr_sch(s) = Min(Nr_per[1,2],Nr_per[2,1])+
	    Min(Nr_per[1,3],Nr_per[3,1])+
            Min(Nr_per[2,3],Nr_per[3,2])+
	    2*Abs(Nr_per[1,2]-Nr_per[2,1])

	Daca pt. orice x<>y s-au efectuat Min(Nr_per[x,y],Nr_per[y,x]) operatii de interschimbare,
secventa rezultata contine Nr_per[1,2]-Nr_per[2,1] triplete de pozitii 1:2,2:3,3:1 (daca
Nr_per[1,2]>Nr_per[2,1]) sau 1:3,2:1,3:2.
	In primul caz algoritmul face interschimbarile 3:1 si 1:2. In urma acestor operatii un ele-
ment 2 ajunge in locul unui element 3, si de aceea in urmatoarea iteratie vor fi executate inter-
schimbarile 2:3 si 3:2. Al doilea caz e similar. Rezulta ca expresia Nr_sch(S) a numarului de in-
terschimbari este corecta.